const common = require('./base/common');

/**
 * 76. 最小覆盖子串
 * 
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let min = Infinity, 
        ansL = -1,
        cnt = new Map(),
        ori = new Map(),
        left = 0,
        right = -1;

    for(let c of t) ori.set(c, (ori.get(c) | 0) + 1);

    function covered() {
        for(let k of ori) {
            if((cnt.get(k[0]) | 0) < k[1]) return false;
        }
        return true;
    }

    while(right < s.length) {
        ++right;

        if(right < s.length && ori.has(s[right])) {
            cnt.set(s[right], (cnt.get(s[right]) | 0) + 1);
        }

        while(covered() && left <= right) {
            if(right - left + 1 < min) {
                min = right - left + 1;
                ansL = left;
            }

            if(ori.has(s[left])) {
                cnt.set(s[left], (cnt.get(s[left]) | 0) - 1);
            }

            left++;
        }
    }
    return ansL < 0? "": s.substr(ansL, min);
};

common.testing([
    ["ADOBECODEBANC", "ABC"],
    ["a", "aa"],
    ["aa", "aa"],
    ["abc", "b"],
    ["bba", "ab"]
], ["BANC", "", "aa", "b", "ba"])(x => minWindow(x[0], x[1]));